#!/usr/bin/env python
#-*- coding:utf-8 -*-

import sys, random, time
from similar import Similarity

def distance(item1, item2):
    #return 1 - Similarity(item1, item2).pearson()
    #return 1 - Similarity(item1, item2).eucdistance()
    #return 1 - Similarity(item1, item2).tanimoto()
    return 1 - Similarity(item1, item2).cosine()

def kmeans(rows, k=4, max_runtimes=100):
    random.seed(time.time())
    if len(rows) == 0:
        return []
    if len(rows) < k:
        return rows

    ranges = []
    for i in range(len(rows[0])):
        ri = [row[i] for row in rows]
        ranges.append( (min(ri), max(ri)) )

    #generate k random cluster centroid
    centroids = []
    for i in range(k):
        centroid = []
        for j in range(len(rows[0])):
            v = random.random()*(ranges[j][1]-ranges[j][0]) + ranges[j][0]
            centroid.append(v)
        centroids.append(centroid)

    lastmatches = None
    for t in range(max_runtimes):
        bestmatches = [[] for i in range(k)]

        for j in range(len(rows)):
            row = rows[j]
            bestmatch = 0
            for i in range(k):
                s = distance(centroids[i], row)
                if s < distance(centroids[bestmatch], row):
                    bestmatch = i
            bestmatches[bestmatch].append(row)

        if bestmatches == lastmatches: break
        lastmatches = bestmatches

        for i in range(k):
            avgs = [0.0] * len(rows[0])
            if len(bestmatches[i]) > 0:
                for item in bestmatches[i]:
                    for m in range(len(item)):
                        avgs[m] += item[m]
                for j in range(len(avgs)):
                    avgs[j] /= len(bestmatches[i])
                centroids[i] = avgs

    errors = []
    for i in range(k):
        error = 0
        for j in bestmatches[i]:
            error += distance(j, centroids[i])
        errors.append(error)
            
    result = []
    for i in range(len(bestmatches)):
        result.append((bestmatches[i], centroids[i], errors[i]))

    return result

# 二分K均值
def bisection_kmeans(rows, k, runtimes):
    clusters = []
    divide_rows = None 
    while True:
        if len(clusters) == 0:
            divide_rows = rows
        else:
            divide_cluster = None
            max_error = 0
            need_remove_clusters = []
            for c in clusters:
                if len(c[0]) == 0:
                    need_remove_clusters.append(c)
                    continue
                error = c[2]
                if error > max_error:
                    max_error = error
                    divide_cluster = c
            divide_rows = divide_cluster[0]
            clusters.remove(divide_cluster)
            for c in need_remove_clusters:
                clusters.remove(c)
                
        min_error = sys.maxint
        min_clusters = None
        for r in range(runtimes):
            bi_clusters = kmeans(divide_rows, 2)
            total_error = sum([c[2] for c in bi_clusters]) 
            if total_error < min_error:
                min_error = total_error
                min_clusters = bi_clusters 

        clusters.extend(min_clusters)
        if len(clusters) == k:
            break

    return clusters

def print_cluster(clusters):
    print "\n\n\n"
    j = 1
    total_error = 0
    for c in clusters:
        print "Cluster %d"%j
        print "Cluster centroid:%s" % c[1]
        print "Cluster errors:%s" % c[2]
        print "Cluster items:"
        for i in c[0]:
            print i
        print "-" * 20
        j += 1
        total_error += c[2]

    print "Total Error:%s" % total_error
    print "-" * 20

if __name__ == "__main__":
    if len(sys.argv) > 1:
        k = int(sys.argv[1])
    rows = []
    f = open("test/game336.txt")
    """
    for i in range(100):
        a = []
        for j in range(36):
            a.append(random.choice([0,0,0,1]))
        f.write("%s\n"%(",".join([str(m) for m in a])))
    """
    lines = f.readlines()
    for line in lines:
        line = line.strip("\n")
        rows.append([int(i) for i in line.split(",")])

    runtimes = 10
    """
    print "Use original k-means"
    min_error = sys.maxint
    min_clusters = None
    for r in range(runtimes):
        clusters = kmeans(rows, k)
        total_error = sum([c[2] for c in clusters]) 
        if total_error < min_error:
            min_error = total_error
            min_clusters = clusters 

    print_cluster(min_clusters)
    """
    
    print "Use bisection k-means"
    gg = []
    import time
    begin = time.time()
    for hh in range(10):
        bi_clusters = bisection_kmeans(rows, k, runtimes)
        #print_cluster(bi_clusters)

        a = [0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0]

        min_distance = sys.maxint
        best_cluster = 0
        for i in range(len(bi_clusters)):
            centroid = bi_clusters[i][1]
            d = distance(a, centroid)
            if d < min_distance:
                min_distance = d
                best_cluster = i

        #print "Test data:", a
        #print "Similar Cluster:"
        #print_cluster([bi_clusters[best_cluster]])

        sect = []
        #print "Intersection"
        for j in bi_clusters[best_cluster][0]:
            s = [i for i in range(len(a)) if (a[i]==1 and j[i]==a[i])]
            sect.append(len(s))
            #print len(s)
        print "Total:%s Average:%s"%(sum(sect), float(sum(sect))/len(sect))
        gg.append(float(sum(sect))/len(sect))

    print "aaa"
    print sum(gg), sum(gg)/10
    print time.time() - begin

                

